package Offer;

/*
    输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
    假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，
    序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    测试用例：
        [1,2,3,4,5]
        [4,5,3,2,1]

    思路:
        遍历pushed数组依次入栈，边入栈边检查出栈序列，如果发现和出栈序列的栈顶元素相同就执行一次出栈操作;
        然后指针j++指向出栈序列的下一个元素；
        如果最后栈内元素为0，则说明该出栈序列是合法的，否则是非法的

* */

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class T31_validateStackSequences {

    @Test
    public void test() {
//        int[] pushed = {1, 2, 3, 4, 5};
//        int[] popped = {4, 3, 5, 1, 2};
        int[] pushed = {0, 1};
        int[] popped = {0, 1};
        System.out.println(validateStackSequences(pushed, popped));
    }

    //效率不太行 61.49%
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed==null&&popped==null){ //两个数组为空的情况
            return true;
        }
        if(pushed!=null&&pushed.length==0&&popped!=null&&popped.length==0){ //两个数组长度为0的情况
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 1, j = 0;
        stack.push(pushed[0]);
        while (j<popped.length){
            Integer top = stack.peek(); //取栈顶元素判断

            if (top != popped[j]) {
                if (i < popped.length) {
                    stack.push(pushed[i++]);
                }
                else {
                    //这个时候pushed数组遍历完了，也就是元素结果入栈或出栈处理，但是popped数组还没遍历完，而且这个时候栈顶元素和popped的元素不相同，说明出栈序列是有问题的
                    return false;
                }
            }else {
                stack.pop();
                if (i < popped.length && stack.size() == 0) {  //如果此时栈内没有元素并且i还没有遍历完
                    stack.push(pushed[i++]);
                }
                j++;
            }
        }
        return stack.size() == 0;
    }


    //优化一下代码逻辑 效率还是没变
    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        for (Integer num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) { //循环
                i++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    //使用LinkedList作为栈效率更好 96%
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        for (Integer num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) { //循环
                i++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}